
package main.old.new_2023.last.month_11;


import java.util.*;

/**
 * @Description: todo 318. 最大单词长度乘积
 * 你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，
 * 并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
 * <p>
 * todo 187. 重复的DNA序列
 * DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。
 * 例如，"ACGAATTCCG" 是一个 DNA序列 。
 * 在研究 DNA 时，识别 DNA 中的重复序列非常有用。
 * 给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
 * <p>
 * todo 334. 递增的三元子序列
 * 给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
 * 如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/
 * @Param:
 * @return:
 **/
public class Solution1106 {

    //递增的三元子序列
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        long[] f = new long[3];
        f[1] = f[2] = (int)1e19;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            if (f[2] < t) {
                return true;
            } else if (f[1] < t && t < f[2]) {
                f[2] = t;
            } else if (f[1] > t){
                f[1] = t;
            }
        }
        return false;
    }

    //重复的DNA序列
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<>();
        //滑动窗口 截取 + hashmap 记录出现次数
        Map<String, Integer> stringCount = new HashMap<>();
        for (int i = 0; i + 9 < s.length(); i++) {
            String temp = s.substring(i, i + 10);
            Integer count = stringCount.getOrDefault(temp, 0);
            if (count == 1) {
                result.add(temp);
            }
            count += 1;
            stringCount.put(temp, count);
        }
        return result;

    }

    //最大单词长度乘积
    public int maxProduct(String[] words) {
        int n = words.length, idx = 0;
        int[] masks = new int[n];
        for (String w : words) {
            int t = 0;
            for (int i = 0; i < w.length(); i++) {
                int u = w.charAt(i) - 'a';
                t |= (1 << u);
            }
            masks[idx++] = t;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if ((masks[i] & masks[j]) == 0) ans = Math.max(ans, words[i].length() * words[j].length());
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution1106 test = new Solution1106();
        test.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
    }
}
